package com.practice.search;

public class Soduku {
	private int N = 9;
	
	public static void main(String[] args) {
		String[] puzzle = new String[]{
				"000050060",
				"000102700",
				"006700030",
				"002000406",
				"004000580",
				"000070000",
				"000508103",
				"050400000",
				"900001000"
		};
		new Soduku().solve(puzzle);
	}
	
	private void solve(String[] puzzle) {
		int[][] a = new int[N][N];
		for (int i=0; i<N; i++) {
			for (int j=0; j<N; j++) {
				a[i][j] = puzzle[i].charAt(j) - '0';
			}
		}
		
		solve(a, 0, 0);
	}
	
	private void solve(int[][] a, int i, int j) {
		if (i == N) {
			print(a);
			return;
		}
		
		if (a[i][j] > 0) {
			next(a, i, j);
		}
		else {
			for (int s=1; s<=9; s++) {
				a[i][j] = s;
				if (test(a)) next(a, i, j);
			}
			a[i][j] = 0;
		}
	}
	
	private boolean test(int[][] a) {
		for (int i=0; i<N; i++) {
			int mask = 0;
			for (int j=0; j<N; j++) {
				if ((mask & (1 << a[i][j])) > 0) return false;
				if (a[i][j] > 0) mask |= 1 << a[i][j];
			}
			
			mask = 0;
			for (int j=0; j<N; j++) {
				if ((mask & (1 << a[j][i])) > 0) return false;
				if (a[j][i] > 0) mask |= 1 << a[j][i];
			}
			
			mask = 0;
			int x = i/3 * 3;
			for (int j=0; j<3; j++, x++) {
				int y = i%3 * 3;
				for (int k=0; k<3; k++, y++) {
					if ((mask & (1 << a[x][y])) > 0) return false;
					if (a[x][y] > 0) mask |= 1 << a[x][y];
				}
			}
		}
		return true;
	}
	
	private void next(int[][] a, int i, int j) {
		if (j+1 < N) {
			solve(a, i, j+1);
		}
		else {
			solve(a, i+1, 0);
		}
	}
	
	private void print(int[][] a) {
		for (int i=0; i<N; i++) {
			for (int j=0; j<N; j++) {
				System.out.print(a[i][j] + " ");
			}
			System.out.println();
		}
	}
}
